class LinkedList{
    constructor() {
        // 添加一个长度属性
        this.size = 0;
        // 声明一个头部节点
        this.head = null;
        // 维护一个尾部节点（添加的时候非常便利）
        this.tail = null;
    }
    // 尾部添加节点
    addLast( item ) {
        // 对参数做一个非空验证
        if ( !item ) { throw new Error('请输入一个正确的节点！') }
        // 创建一个节点
        let node = new Node(item);
        // 判断链表是否为空
        if ( this.size === 0 ) {
            // 更新尾部节点，更新头部节点
            this.tail = this.head = node;
        } else {
            // 设置尾部节点的引用
            this.tail.next = node;
            // 将最新的尾部节点更新到tail
            this.tail = node
        }
        // 更新一下长度
        this.size++;
    }
    // 头部添加节点
    addFirst( item ) {
        // 对参数做一个非空验证
        if ( !item ) { throw new Error('请输入一个正确的节点！') }
        // 创建一个node节点
        let node = new Node(item);
        // 判断当前链表是否为空
        if ( this.size === 0 ) {
            this.head = this.tail = node;
        } else {
            // 将整个链表作为新节点的next引用
            node.next = this.head;
            // 将node赋值给head
            this.head = node;
        }
        // 更新一下长度
        this.size++
    }
    // 查找节点
    find( item ) {
        // 对参数做一个非空验证
        if ( !item ) { throw new Error('请输入一个正确的节点！') }
        // 获取到整个节点
        let linkedList = this.head;
        // 循环判断
        while ( linkedList && linkedList.next && linkedList.value !== item ){
            linkedList = linkedList.next;
        }
        return linkedList
    }
    // 删除最后一个节点
    removeFirst (){
        // 定义一个返回值
        let res = null;
        // 判断当前链表不为空
        if ( this.size !== 0 ) {
            res = this.head;
            // 跳过head节点，将head指向head的next
            this.head = this.head.next;
            res.next = null;
            // 维护一下长度
            this.size--;
            // 判断删除完，链表为空，清空一下尾部节点的引用
            this.tail = this.size ? this.tail : null;
        } else {
            // 如果链表为空，调用删除操作，就报一个警告
            throw new Error('链表为空，不能执行删除操作！')
        }
        return res
    }
    // 删除尾部节点
    removerLast() {
        // 定义一个返回值
        let res = null;
        // 拿到所有节点
        let linkedList = this.head;
        // 判断当前链表是否只有一个节点
        if ( this.size === 1 ) {
            res = this.head;
            this.head = this.tail = null;
            res.next = null;
        }
        // 判断是链表为为空
        if ( this.size === 0 ) {
            // 如果链表为空，调用删除操作，就报一个警告
            throw new Error('链表为空，不能执行删除操作！')
        } else {
            // 循环找倒数第二个节点
            while ( linkedList && linkedList.next && linkedList.next.next ){
                linkedList = linkedList.next;
            }
            res = linkedList.next;
            // 将最后一个引用置为空
            linkedList.next = null;
            // 维护一下尾部节点
            this.tail = linkedList;
            // 维护一下长度
            this.size--;
        }
        return res
    }
    // 删除指定节点
    remover( item ){
        // 定义一个返回值
        let res = null;
        // 对参数做一个非空验证
        if ( !item ) { throw new Error('请输入一个正确的节点！') }
        // 拿到整个链表
        let linkedList = this.head;
        // 判断链表只有一个节点
        if ( this.size === 1 && linkedList.value === item ) {
            res = linkedList;
            // 维护一下头部节点和尾部节点
            this.head = this.tail =  null;

        } else {
            // 循环找到指定节点的父级
            while ( linkedList && linkedList.next && linkedList.next.value !== item ) {
                linkedList = linkedList.next;
            }
            // 判断是否存在
            if ( linkedList && linkedList.next ) {
                // 存下删除节点
                res = linkedList.next;
                // 删除指定节点
                linkedList.next = linkedList.next.next;

            } else {
                throw new Error('链表中没有该节点，不能执行删除操作！')
            }
        }

        // 判断一下删除节点是否为最后一个节点
        this.tail = linkedList.next ? this.tail : null;
        // 删除节点的next指向清空
        res.next = null;
        // 维护一下
        this.size--;
        return res
    }
    // 验证链表为空
    isEmpty() {
        return this.size === 0
    }
    // 指定位置插入节点
    insert ( item, ele ) {
        // 验证两个参数不能为空
        if ( !item || !ele ) { throw new Error('请输入一个正确的节点或者查找元素！') }
        // 拿到整个链表
        let linkedList = this.head;
        // 循环查找匹配
        while ( linkedList && linkedList.value !== item ) {
            linkedList = linkedList.next;
        }
        // 验证结果，结果只能是两个，找到，没找到
        if ( linkedList ) {
            // 生成一个节点
            let node = new Node(ele);
            // 将匹配到的节点的next引用指向新节点的next引用
            node.next = linkedList.next;
            // 将新节点赋值给 匹配到的节点
            linkedList.next = node;
            // 判断一下是否是插入到了最后一个元素
            this.tail = node.next ? this.tail : node;
            // 维护一下长度
            this.size++;
        } else {
            throw new Error('没有匹配到需要插入位置的元素！')
        }
    }
    // 获取最后一个节点
    findLast() {
        return this.tail
    }
    // 展开链表
    dir(){
        // 获取整个链表
        let linkedList = this.head;
        // 定义一个返回值
        let res = linkedList ? linkedList.value : '';
        // 循环获取整个链表的数据
        while ( linkedList.next ) {
            res += '->' + linkedList.next.value;
            linkedList = linkedList.next;
        }
        // 返回数据
        return res
    }
}
class Node{
    constructor( data ) {
        // 节点的value
        this.value = data;
        // 节点的下一个引用指向
        this.next = null;
    }
}
